﻿#include <iostream>
#include <vector>

using namespace std;

static int getNo(int n, const int* numbers, const size_t numberSize, int numberIndex)
{
	if (n == 1) return 1;

	if (numberIndex >= numberSize)
	{
		numberIndex = 0;
	}

	int m = numbers[numberIndex];
	int newNo = getNo(n - 1, numbers, numberSize, numberIndex + 1);
	return (newNo + m - 1) % n + 1;
}

static int finalPersonNo(int n, const int* numbers, const size_t numberSize)
{
	int finalNo = getNo(n, numbers, numberSize, 0);
	return finalNo - 1;
}

/**
 * 某公司招聘，有n个人入围，HR在黑板上依次写下m个正整数A1、A2、......、Am，然后让这n个人围城一个圈，并按照顺时针顺序为他们编号0、1、2、......、n-1。录取规则是：
 * 第一轮从0号的人开始，取用黑板上的第一个数字，也就是A1，黑板上的数字按次序循环取用，即如果某轮用了第m个，则下一轮需要用第一个；如果某轮用到第k个，则下一轮需要用第k+1个(k<m)
 * 每一轮按照黑板上的次序取用到一个数字Ax，淘汰掉从当前轮到的人开始按照顺时针顺序数到的第Ax个人，下一轮开始时轮到的人即为被淘汰掉的人的顺时针顺序下一个人
 * 被淘汰的人直接回家，所以不会被后续轮次计数时数到
 * 经过n-1轮后，剩下的最后1人被录取，所以最后被录取的人的编号与(n,m,A1,A2,......,Am)相关。
 * 输入描述:
 * 第一行是一个正整数N，表示有N组参数
 * 从第二行开始，每行有若干个正整数，依次存放n、m、A1、......、Am, 一共有N行，也就是上面的N组参数。
 * 输出描述:
 * 输出有N行，每行对应相应的那组参数确定的录取之人的编号。
 * 
 * 思路：
 * 借鉴约瑟夫环问题的公式
 */
int main_recruitmentKeepOnlyOne()
{
	char input[][0xff + 1] =
	{
		"3",
		"6 3 1 2 3",
		"4 2 10 11",
		"3 2 1 2",
	};

	int instanceCount = 0;
	sscanf_s(input[0], "%d", &instanceCount);

	int n;
	int numberSize;
	int* numbers = nullptr;
	int index;
	int inputLen;
	char cur;
	char* curInput = nullptr;
#define NUMTEXT_SIZE 100
	char numText[NUMTEXT_SIZE];
	int num;
	bool nInited = false;
	bool nCountInited = false;
	int numIndex;
	int numberIndex;

	for (int i = 0; i < instanceCount; i++)
	{
		curInput = input[1 + i];
		inputLen = strlen(curInput);
		numbers = nullptr;
		numberSize = 0;
		index = 0;
		numIndex = 0;
		numberIndex = 0;
		nInited = false;
		nCountInited = false;
		memset(numText, 0, NUMTEXT_SIZE);

		while (index < inputLen)
		{
			cur = curInput[index];
			if (cur == ' ')
			{
				sscanf_s(numText, "%d", &num);
				if (!nInited)
				{
					nInited = true;
					n = num;
				}
				else if (!nCountInited)
				{
					nCountInited = true;
					numberSize = num;
					numbers = (int*)malloc(numberSize * sizeof(int));
					memset(numbers, 0, numberSize * sizeof(int));
				}
				else
				{
					numbers[numberIndex++] = num;
				}

				memset(numText, 0, NUMTEXT_SIZE);
				numIndex = 0;
			}
			else
			{
				numText[numIndex++] = cur;
			}
			
			++index;
		}

		sscanf_s(numText, "%d", &num);
		if (numbers)
		{
			numbers[numberIndex] = num;
		}

		int no = finalPersonNo(n, numbers, numberSize);
		printf("[%d]:%d\n", i, no);
		free(numbers);
	}

	return 0;
}